#include "main/utils.h"
#include "lib/binary_tree.h"
using namespace std;

vector<int> maxOfLine(BinaryTreeNode* root) {
  if (!root)
    return {};

  vector<int> ret;
  deque<BinaryTreeNode*> node_deque;
  node_deque.push_back(root);
  int cur_num = 1;
  int next_num = 0;
  int cur_max = INT_MIN;
  while (!node_deque.empty()) {
    auto front_node = node_deque.front();
    if (front_node->value > cur_max)
      cur_max = front_node->value;

    if (front_node->left) {
      node_deque.push_back(front_node->left);
      ++next_num;
    }
    if (front_node->right) {
      node_deque.push_back(front_node->right);
      ++next_num;
    }

    node_deque.pop_front();
    --cur_num;
    if (cur_num == 0) {
      cur_num = next_num;
      next_num = 0;
      ret.push_back(cur_max);
      cur_max = INT_MIN;
    }
  }
  return ret;
}

vector<int> maxOfLine1(BinaryTreeNode* root) {
  if (!root)
    return {};

  deque<BinaryTreeNode*> node_deque1;
  deque<BinaryTreeNode*> node_deque2;
  node_deque1.push_back(root);
  int cur_max = INT_MIN;
  vector<int> ret;
  while (!node_deque1.empty()) {
    auto front_node = node_deque1.front();
    if (front_node->value > cur_max) {
      cur_max = front_node->value;
    }

    if (front_node->left) {
      node_deque2.push_back(front_node->left);
    }
    if (front_node->right) {
      node_deque2.push_back(front_node->right);
    }

    node_deque1.pop_front();
    if (node_deque1.empty()) {
      swap(node_deque1, node_deque2);
      ret.push_back(cur_max);
      cur_max = INT_MIN;
    }
  }
  return ret;
}

int main() {
  vector<int> vec = {4, 3, 2, 5, 1, 9};
  BinaryTreeNode* root = CreateBinaryTree(vec);
  vector<int> ret = maxOfLine(root);
  printVec("maxOfLine", ret);

  vector<int> ret1 = maxOfLine1(root);
  printVec("maxOfLine1", ret1);

  return 0;
}
